/**
 * @author AlfredCai
 */
public class Quick {
    private static int partition(int[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        int v = a[i];
        int temp;
        while (true) {
            while (a[++i] < v) if (i == hi) break;
            while (v < a[--j]) if (j == lo) break;
            if (i >= j) break;
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        temp = a[lo];
        a[lo] = a[j];
        a[j] = temp;
        return j;
    }

    private static void sort(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    public static void sort(int[] array) {
        sort(array, 0, array.length - 1);
    }


}
